﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
/*
==========================================================
描述
给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1
2.如果无法跳跃(即数组长度为0)，也请返回-1
3.数据保证返回的结果不会超过整形范围，即不会超过2^{31}-12
31
 −1
数据范围:
0<=nums.length<= 10^5
0<=nums[i]<=1000
输入描述：
第一行输入一个正整数 n 表示数组 nums的长度
第二行输入 n 个整数，表示数组 nums 的所有元素的值
输出描述：
输出能获得的最多的积分
==========================================================
*/

int Max(int x, int y)       //返回可达到最大距离函数
{
	return x > y ? x : y;
}
int main()
{
	int n = 0;          //代表格数
	int i = 0;          //用于循环遍历
	int k = 0;          //表示最大跳跃距离
	scanf("%d", &n);
	int* num = (int*)malloc(n * sizeof(int));
	int* dp = (int*)malloc(n * sizeof(int));        //存储每个子问题即跳到第i格的最大积分
	for (i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	dp[0] = num[0];                         //赋初值，跳到第1格的最大积分即为自身
	if (n == 0)                             //空数组
	{
		printf("-1\n");
		return 0;
	}
	if (n == 1)                             //只有一个格子，最大积分即为自身
	{
		printf("%d\n", dp[0]);
		return 0;
	}
	for (i = 0; i < n; i++)                 //自下而上遍历，寻找最大距离
	{
		if (i <= k)                         //子问题成立
		{
			int j = 0;
			k = Max(k, i + num[i]);         //更新最大距离
			for (j = i - 1; j >= 0; j--)    //自上而下，求出子问题的最大积分
			{
				if (j + num[j] >= i)        //找到可跳到i最近的格子j
				{
					dp[i] = dp[j] + num[i]; //第i格的最大积分即为j的最大积分加上num[i]
					break;
				}
			}
		}
		else                                //子问题不成立，无法跳到第i格
		{
			printf("-1\n");
			return 0;
		}
	}
	printf("%d", dp[n - 1]);                //所有子问题均成立，则到终点最大积分就为dp的最后 
	                                        //一个元素
	free(num);
	free(dp);
	return 0;
}